//要求：根据前序遍历和中序遍历得到树
#include <iostream>
#include <vector>

using namespace std;
struct TreeNode{
	TreeNode *left;
	TreeNode *right;
	int val;
	TreeNode(int v):left(NULL),right(NULL),val(v){}
};


TreeNode *buildTree(vector<int> &preorder, vector<int> &midorder)
{
	if (preorder.size() == 0 || midorder.size() == 0) return NULL;
	TreeNode *root = new TreeNode(preorder[0]);
	int rv = preorder[0];
	int i;
	for (i = 0; i < midorder.size(); ++i)
	{
		if (midorder[i] == rv)
			break;
	}
	vector<int> p1(preorder.begin() + 1, preorder.begin() + i + 1);
	vector<int> m1(midorder.begin(), midorder.begin() + i);
	
	root->left = buildTree(p1, m1);
	
	vector<int> p2(preorder.begin() + 1 + i, preorder.end());
	vector<int> m2(midorder.begin() + i + 1, midorder.end());
	root->right = buildTree(p2, m2);
	
	return root;
}

vector<int> backod;
void backorder(TreeNode *root)
{
	if (root == NULL) return ;
	backorder(root->left);
	backorder(root->right);
	backod.emplace_back(root->val);
	
}

int main()
{
//	vector<int> p{3, 9, 20, 15, 7};
//	vector<int> m{9, 3, 15, 20, 7};
	vector<int> p{1, 2, 3, 5, 4, 6};
	vector<int> m{5, 3, 2, 4, 6, 1};
	TreeNode *root = buildTree(p, m);
	backorder(root);
	for (int i : backod)
		cout << i << " ";
	cout << endl;
	
	return 0;
} 
 